The operating system is the most important software running on a computer. Every general purpose computer must have an operating system to run other programs. Operating systems typically perform basic tasks, such as recognizing input from the keyboard, sending output to the display screen, keeping track of files and directories on the disc, and controlling peripheral devices such as disc drives and printers. For more complex systems, the operating system has even greater responsibilities and powers. It makes sure that different programs and users running at the same time do not interfere with each other. The operating system is also typically responsible for security, ensuring that unauthorized users do not access the system.
Operating systems can be classified as multi-user operating systems, multi-processor operating systems, multi-tasking operating systems, and real-time operating systems. A multi-user operating system allows two or more users to run programs at the same time. Some operating systems permit hundreds or even thousands of concurrent users. A multi-processing program allows a single user to run two or more programs at the same time. Each program being executed is called a process. Most multi-processing systems support more than one user. A multi-tasking system allows a single process to run more than one task. In common terminology, the terms multi-tasking and multi-processing are often used interchangeably even though they have slightly different meanings. Multi-tasking is the ability to execute more than one task at the same time, a task being a program. In multi-tasking, only one central processing unit is involved, but it switches from one program to another so quickly that it gives the appearance of executing all of the programs at the same time. There are two basic types of multi-tasking, preemptive and cooperative. In preemptive multi-tasking, the operating system parcels out CPU time slices to each program. In cooperative multi-tasking, each program can control the CPU for as long as it needs it. If a program is not using the CPU however, it can allow another program to use it temporarily. For example, the OS/2 (TM) and UNIX (TM) operating systems use preemptive multi-tasking, whereas the Multi-Finder (TM) operating system for Macintosh (TM) computers uses cooperative multi-tasking. Multi-processing refers to a computer system's ability to support more than one process or program at the same time. Multi-processing operating systems enable several programs to run concurrently. Multi-processing systems are much more complicated than single-process systems because the operating system must allocate resources to competing processes in a reasonable manner. A real-time operating system responds to input instantaneously. General purpose operating systems such as DOS and UNIX are not real-time.
Operating systems provide a software platform on top of which application programs can run. The application programs must be specifically written to run on top of a particular operating system. The choice of the operating system therefore determines to a great extent the applications which can be run. For IBM compatible personal computers, example operating systems are DOS, OS/2 (TM), AIX (TM), and XENIX (TM).
A user normally interacts with the operating system through a set of commands. For example, the DOS operating system contains commands such as COPY and RENAME for copying files and changing the names of files, respectively. The commands are accepted and executed by a part of the operating system called the command processor or command line interpreter.
There are many different operating systems for personal computers such as CP/M (TM), DOS, OS/2 (TM), UNIX (TM), XENIX (TM), and AIX (TM). CP/M was one of the first operating systems for small computers. CP/M was initially used on a wide variety of personal computers, but it was eventually overshadowed by DOS. DOS runs on all IBM compatible personal computers and is a single user, single tasking operating system. OS/2, a successor to DOS, is a relatively powerful operating system that runs on IBM compatible personal computers that use the Intel 80286 or later microprocessor. OS/2 is generally compatible with DOS but contains many additional features, for example it is multi-tasking and supports virtual memory. UNIX and UNIX-based AIX run on a wide variety of personal computers and work stations. UNIX and AIX have become standard operating systems for work stations and are powerful multi-user, multi-processing operating systems.
In 1981 when the IBM personal computer was introduced in the United States, the DOS operating system occupied approximately 10 kilobytes of storage. Since that time, personal computers have become much more complex and require much larger operating systems. Today, for example, the OS/2 operating system for the IBM personal computers can occupy as much as 22 megabytes of storage. Personal computers become ever more complex and powerful as time goes by and it is apparent that the operating systems cannot continually increase in size and complexity without imposing a significant storage penalty on the storage devices associated with those systems.
It was because of this untenable growth rate in operating system size, that the MACH project was conducted at the Carnegie Mellon University in the 1980's. The goal of that research was to develop a new operating system that would allow computer programmers to exploit modern hardware architectures emerging and yet reduce the size and the number of features in the kernel operating system. The kernel is the part of an operating system that performs basic functions such as allocating hardware resources. In the case of the MACH kernel, five programming abstractions were established as the basic building blocks for the system. They were chosen as the minimum necessary to produce a useful system on top of which the typical complex operations could be built externally to the kernel. The Carnegie Mellon MACH kernel was reduced in size in its release 3.0, and is a fully functional operating system called the MACH microkernel. The MACH microkernel has the following primitives: the task, the thread, the port, the message, and the memory object.
The traditional UNIX process is divided into two separate components in the MACH microkernel. The first component is the task, which contains all of the resources for a group of cooperating entities. Examples of resources in a task are virtual memory and communications ports. A task is a passive collection of resources; it does not run on a processor.
The thread is the second component of the UNIX process, and is the active execution environment. Each task may support one or more concurrently executing computations called threads. For example, a multi-threaded program may use one thread to compute scientific calculations while another thread monitors the user interface. A MACH task may have many threads of execution, all running simultaneously. Much of the power of the MACH programming model comes from the fact that all threads in a task share the task's resources. For instance, they all have the same virtual memory (VM) address space. However, each thread in a task has its own private execution state. This state consists of a set of registers, such as general purpose registers, a stack pointer, a program counter, and a frame pointer.
A port is the communications channel through which threads communicate with each other. A port is a resource and is owned by a task. A thread gains access to a port by virtue of belonging to a task. Cooperating programs may allow threads from one task to gain access to ports in another task. An important feature is that they are location transparent. This capability facilitates the distribution of services over a network without program modification.
The message is used to enable threads in different tasks to communicate with each other. A message contains collections of data which are given classes or types. This data can range from program specific data such as numbers or strings to MACH related data such as transferring capabilities of a port from one task to another.
A memory object is an abstraction which supports the capability to perform traditional operating system functions in user level programs, a key feature of the MACH microkernel. For example, the MACH microkernel supports virtual memory paging policy in a user level program. Memory objects are an abstraction to support this capability.
All of these concepts are fundamental to the MACH microkernel programming model and are used in the kernel itself. These concepts and other features of the Carnegie Mellon University MACH microkernel are described in the book by Joseph Boykin, et al, "Programming Under MACH", Addison Wessely Publishing Company, Incorporated, 1993.
Additional discussions of the use of a microkernel to support a UNIX personality can be found in the article by Mike Accetta, et al, "MACH: A New Kernel Foundation for UNIX Development", Proceedings of the Summer 1986 USENIX Conference, Atlanta, Georgia. Another technical article on the topic is by David Golub, et al, "UNIX as an Application Program", Proceedings of the Summer 1990 USENIX Conference, Anaheim, Calif.
The above cited, copending patent application by Guy G. Sotomayor, Jr., James M. Magee, and Freeman L. Rawson, III, describes the Microkernel System 115 shown in FIG. 1, which is a new foundation for operating systems. The Microkernel System 115 provides a concise set of kernel services implemented as a pure kernel and an extensive set of services for building operating system personalities implemented as a set of user-level servers. The Microkernel System 115 is made up of many server components that provide the various traditional operating system functions and that are manifested as operating system personalities. The Microkernel System 115 uses a client/server system structure in which tasks (clients) access services by making requests of other tasks (servers) through messages sent over a communication channel. Since the microkernel 120 provides very few services of its own (for example, it provides no file service), a microkernel 120 task must communicate with many other tasks that provide the required services.
In the Microkernel System 115, each task has its own virtual address space defined for itself. When a thread of the task computes an address value, it is a virtual address in the virtual address space uniquely defined for that task. In order to access the real, physical memory for writing or reading data, the virtual address must be converted into a real, physical address.
A mapping table called a PMAP converts the virtual address value into a physical address of a cache object in the memory that contains a page of data to be used by the task. There is a PMAP table associated with each task (or if there is a group of several copies of a task, one PMAP table is associated with the group.) Each PMAP table contains an address translation from the virtual address to the real, physical address in the real, physical memory where the data is to be read or written. If the PMAP for a task fails to contain the translated address corresponding to the virtual address, then a page fault occurs. In response to the page fault, the memory manager server swaps the requested page of data from the backing store, such as a disk drive, to the real, physical RAM memory.
The above referenced patent application by Guy G. Sotomayor, Jr., James M. Magee, and Freeman L. Rawson, IlIl describes the microkernel 120 as defining a first pointer for the task that points to a template region. Within the template region, there are second pointers that point directly or indirectly to the mapping table of the PMAP. The PMAP converts the virtual address value of the second pointers, into a physical address of a cache object in the memory that contains a page of data to be used by the task. From time to time, changes are desired to be made in the data resources of a task. This is accomplished by changing the virtual address value represented by the second pointers in the template region. The changed second pointers can point to different translation values in the PMAP, resulting in the addressing of different pages or cache objects, as is desired. But, no changes are necessary to the contents of the task, itself. Task resources, such as data in cache objects, are addressed by the task through the second pointers in the template region. If the microkernel 120 has defined a plurality of tasks from the same template region, then changing the second pointers in the template region will result in a global change in the resources available to the plurality of tasks pointing to that template region. The data pages addressed by the tasks can be changed with a single change to the second pointers in the template region, instead of changing the contents of each one of the tasks. If the physical copy of one page of data belonging to a task is swapped out of the RAM, the PMAP entry for that page of data is also removed. The next time that task and its thread use the pointer to the missing entry in the PMAP in an attempt to access the missing page of data, a page fault occurs. In resolving a page fault, the microkernel 120 in FIG. 1, sends a message to the default pager 144. The default pager 144 then reads into the RAM the page that the kernel needs from a hard disk. Although the page fault is being resolved on behalf of a user task, the kernel is the sender of the message.
The Microkernel System 115 needs services to program the memory management unit (MMU) for the processor that it is running on. One advanced technology processor that can take full advantage of the capabilities of the Microkernel System 115 is the PowerPC (TM). The PowerPC is an advanced RISC (reduced instruction set computer) architecture, described in the book: IBM Corporation, "The PowerPC Architecture", Morgan-Kaufmann, San Francisco, 1994. Another description of the PowerPC is provided in the article: Keith Diefendorff, Rich Oehler, and Ron Hochsprung, "Evolution of the PowerPC Architecture", IEEE Micro, Apr. 1994, pp. 34-49. The PowerPC was designed with its architecture divided into three parts or "books." Book 1 deals with those features that will not change over time, such as the user instruction set architecture, instruction definitions, opcode assignments, register definitions, etc. Book 2 deals with those features important to the operation of the processor in a multiprocessing environment, such as the memory model, consistency, atomicity and aliasing. Book 3 deals with the operating environment architecture. These are features that are not directly visible to the user, but instead are the exclusive domain of the operating system. Within this part of the architecture is the definition of the virtual-to-physical address translation and the method of exception handling. Because Book 3 features are supervisor privileged, it is possible to design a PowerPC processor according to an entirely different set of Book 3 features, and yet maintain user application compatibility.
The PowerPC provides a unique three-level, demand-paged virtual memory operating environment as a part of its existing Book 3 features. Each program has its own separate, linear logical address space. Logical program addresses are mapped into a very large, segmented virtual address space shared by all processes. The architecture specifies a set of sixteen segment registers for mapping the logical addresses into physical addresses. The processor outputs a 32-bit effective address, with the four high-order bits identifying the segment register number. There are two steps in the segmented address translation. The first step is to convert the effective address to a virtual address. This involves concatenating the page index and byte offset of the effective address, with a 24-bit virtual segment ID (VSID) that is assigned by the operating system. The VSID is loaded into one of sixteen segment registers, and serves as an offset into the large virtual address space. This virtual memory structure enables a variety of operating system addressing, such as object-based addressing to support very large programs. The second step is to convert the virtual address to a real address. This involves translating the virtual address through an inverted page table structure to the final physical memory address. Pages in the virtual address space are dynamically mapped onto the physical address space as needed. As part of the second step, a page table containing page table entries, is accessed to obtain the mapping between a virtual page number and a real page number. The page table contains a number of page table entry groups (PTEGs). A PTEG contains eight page table entries (PTEs) of eight bytes each. PTEGs are the entry points for searches of the page table. Each page table entry (PTE) maps one virtual page number (VPN) to one real page number (RPN). The number of entries in the page table directly affects performance because it influences the hit ratio in the page table and thus the rate of page fault interrupts. If the table is too small, it is possible that not all of the virtual pages that actually have real pages assigned can be mapped via the page table. The PowerPC defines a limited set of active, page table entries (PTES) to map the virtual address into the real, physical address.
The problem in adapting the Microkernel System 115 to the PowerPC, is that the limited number of PTEs in the page table of the PowerPC are rapidly used up by the proliferation of tasks and threads when the Microkernel System 115 is operating. When all of the active PTEs are used up, a new read or write access will cause a page fault. Even though the physical page is actually present in the RAM, the absence of the correct PTE from the page table will be inferred by the system as a page fault. This will require the PowerPC to evict one of the active PTEs from the page table, install a new PTE in the page table, access the backing store, and swap into the RAM the apparently missing page of data. This imposes a performance drag on the overall operation of the PowerPC when running the Microkernel System 115.